package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/8/3 0003.
 */

/**
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 */
public class 合并两个排序的链表 {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);

        node1.next = node3;
        node3.next = node5;
        node5.next = node7;

        node2.next = node4;
        node4.next = node6;
        node6.next = node8;

        ListNode result = Merge(node1, node2);
        print(result);
    }

    /**
     * 假设将list2中的所有元素都搬迁到list1上
     */
    public static ListNode Merge(ListNode list1, ListNode list2) {
        //null值检测。
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        else {
            ListNode result = list1;
            ListNode newNode2;
            while (list1.next != null) {
                //当list2的值满足条件时，将此节点插入list1中
                if (list2 != null && list1.val <= list2.val && list1.next.val >= list2.val) {
                    newNode2 = list2;
                    list2 = list2.next;
                    newNode2.next = list1.next;
                    list1.next = newNode2;
                    list1 = list1.next;
                }
                list1 = list1.next;
            }
            //如果list1遍历完了，list2还不为空，就把list2剩余的元素都放到list1尾部。
            if (list2 != null) {
                list1.next = list2;
            }
            return result;
        }
    }

    /**
     * 递归版本，但不推荐使用，因为如果链表比较长，比较耗空间。反而增加了复杂度。
     */
    public ListNode Merge2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge2(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge2(list1, list2.next);
            return list2;
        }
    }

    public static void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val + "->");
            node = node.next;
        }
    }

    private static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
}
